﻿#include<stdio.h>
typedef char datatype;
typedef struct stack{
	datatype * a;
	int capacity;
	int top;
}st;
void stackinit(st* ps)
{
	assert(ps);
	ps->a = (datatype*)malloc(sizeof(datatype) * 4);
	if (ps->a == NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}
	ps->capacity = 4;
	ps->top = 0;
}
void stackpush(st* ps, datatype x)
{
	assert(ps);
	datatype* cmp = (datatype*)realloc(ps->a, ps->capacity * sizeof(datatype) * 2);
	if (cmp == NULL)
	{
		printf("realloc fail\n");
		return;
	}
	else
	{
		ps->a = cmp;
		ps->capacity *= 2;
	}
	ps->a[ps->top] = x;//将值给数组
	ps->top++;//然后栈顶个数++
}
void stackpop(st* ps)
{
	assert(ps);
	ps->top--;
}
datatype popdata(st* ps)
{
	assert(ps);
	assert(ps->top);
	return ps->a[ps->top - 1];
}
 int stackempty(st* ps)
{
	assert(ps);
	return ps->top == 0;
}
void stackdestory(st* ps)
{
	assert(ps);
	ps->capacity = ps->top = 0;
	ps->a = NULL;
	return;
}
 int isValid(char* s)
{
	st ST;
	stackinit(&ST);
	while (*s != '\0')
	{
		switch (*s)
		{
			case '{':
			case '[' :
				case '(' :
			{
				stackpush(&ST, *s);//入栈
				break;
			}
			case '}' :
				case ']' :
				case ')' :
			{
				if (stackempty(&ST))
				{
					stackdestory(&ST);
					return 0;
				}
				char top = popdata(&ST);//取上述入栈的栈顶元素
				stackpop(&ST);//删除数据
				//开始不匹配判断
				if((*s == '}' && top != '{')
					|| (*s == ']' && top != '[')
					|| (*s == ')' && top != ')'))
				{
					stackdestory(&ST);
					return 0;
				}
				else//匹配
				{
					++s;
				}
				break;
			}
		default:
			break;
		}
	}
	stackdestory(&ST);
	return 1;
}
int main()
{



	return 0;
}